home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / makeindex / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-04-26  |  5.6 KB  |  229 lines
  1. /*
  2.  * qsort.c:
  3.  * Our own version of the system qsort routine which is faster by an average
  4.  * of 25%, with lows and highs of 10% and 50%.
  5.  * The THRESHold below is the insertion sort threshold, and has been adjusted
  6.  * for records of size 48 bytes.
  7.  * The MTHREShold is where we stop finding a better median.
  8.  */
  9.  
  10. /* #include <stdio.h> -- mkind.h includes this */
  11. #include "mkind.h"            /* only for type declarations */
  12.  
  13. #define        THRESH        4    /* threshold for insertion */
  14. #define        MTHRESH        6    /* threshold for median */
  15.  
  16. static int (*qcmp) ();        /* the comparison routine */
  17. static int qsz;            /* size of each record */
  18.  
  19. static int thresh;        /* THRESHold in chars */
  20. static int mthresh;        /* MTHRESHold in chars */
  21.  
  22.  
  23.  
  24. /*
  25.  * qsort:
  26.  * First, set up some global parameters for qst to share.  Then, quicksort
  27.  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  28.  * It's not...
  29.  */
  30.  
  31. void
  32. qsort(base, n, size, compar)
  33. char *base;
  34. int n;
  35. int size;
  36. int (*compar) ();
  37. {
  38.     register char *i;
  39.     register char *j;
  40.     register char *lo;
  41.     register char *hi;
  42.     register char *min;
  43.     register char c;
  44.     char *max;
  45.  
  46.     if (n <= 1)
  47.     return;
  48.     qsz = size;
  49.     qcmp = compar;
  50.     thresh = qsz * THRESH;
  51.     mthresh = qsz * MTHRESH;
  52.     max = base + n * qsz;
  53.     if (n >= THRESH)
  54.     {
  55.     qst(base, max);
  56.     hi = base + thresh;
  57.     }
  58.     else
  59.     {
  60.     hi = max;
  61.     }
  62.     /* First put smallest element, which must be in the first THRESH, in the
  63.        first position as a sentinel.  This is done just by searching the
  64.        first THRESH elements (or the first n if n < THRESH), finding the min,
  65.        and swapping it into the first position. */
  66.     for (j = lo = base; (lo += qsz) < hi;)
  67.     {
  68.     if ((*qcmp) (j, lo) > 0)
  69.         j = lo;
  70.     }
  71.     if (j != base)
  72.     {                /* swap j into place */
  73.     for (i = base, hi = base + qsz; i < hi;)
  74.     {
  75.         c = *j;
  76.         *j++ = *i;
  77.         *i++ = c;
  78.     }
  79.     }
  80.     /* With our sentinel in place, we now run the following hyper-fast
  81.        insertion sort.  For each remaining element, min, from [1] to [n-1],
  82.        set hi to the index of the element AFTER which this one goes. Then, do
  83.        the standard insertion sort shift on a character at a time basis for
  84.        each element in the frob. */
  85.     for (min = base; (hi = min += qsz) < max;)
  86.     {
  87.     while ((*qcmp) (hi -= qsz, min) > 0);
  88.     if ((hi += qsz) != min)
  89.     {
  90.         for (lo = min + qsz; --lo >= min;)
  91.         {
  92.         c = *lo;
  93.         for (i = j = lo; (j -= qsz) >= hi; i = j)
  94.             *i = *j;
  95.         *i = c;
  96.         }
  97.     }
  98.     }
  99. }
  100.  
  101.  
  102.  
  103. /*
  104.  * qst:
  105.  * Do a quicksort
  106.  * First, find the median element, and put that one in the first place as the
  107.  * discriminator.  (This "median" is just the median of the first, last and
  108.  * middle elements).  (Using this median instead of the first element is a big
  109.  * win).  Then, the usual partitioning/swapping, followed by moving the
  110.  * discriminator into the right place.  Then, figure out the sizes of the two
  111.  * partions, do the smaller one recursively and the larger one via a repeat of
  112.  * this code.  Stopping when there are less than THRESH elements in a partition
  113.  * and cleaning up with an insertion sort (in our caller) is a huge win.
  114.  * All data swaps are done in-line, which is space-losing but time-saving.
  115.  * (And there are only three places where this is done).
  116.  */
  117.  
  118. static void
  119. qst(base, max)
  120. char *base;
  121. char *max;
  122. {
  123.     register char *i;
  124.     register char *j;
  125.     register char *jj;
  126.     register char *mid;
  127.     register int ii;
  128.     register char c;
  129.     char *tmp;
  130.     int lo;
  131.     int hi;
  132.  
  133.     lo = max - base;        /* number of elements as chars */
  134.     do
  135.     {
  136.     /* At the top here, lo is the number of characters of elements in the
  137.        current partition.  (Which should be max - base). Find the median
  138.        of the first, last, and middle element and make that the middle
  139.        element.  Set j to largest of first and middle.  If max is larger
  140.        than that guy, then it's that guy, else compare max with loser of
  141.        first and take larger.  Things are set up to prefer the middle,
  142.        then the first in case of ties. */
  143.     mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
  144.     if (lo >= mthresh)
  145.     {
  146.         j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
  147.         if ((*qcmp) (j, (tmp = max - qsz)) > 0)
  148.         {
  149.         j = (j == jj ? i : jj);    /* switch to first loser */
  150.         if ((*qcmp) (j, tmp) < 0)
  151.             j = tmp;
  152.         }
  153.         if (j != i)
  154.         {
  155.         ii = qsz;
  156.         do
  157.         {
  158.             c = *i;
  159.             *i++ = *j;
  160.             *j++ = c;
  161.         } while (--ii);
  162.         }
  163.     }
  164.     /* Semi-standard quicksort partitioning/swapping */
  165.     for (i = base, j = max - qsz;;)
  166.     {
  167.         while (i < mid && (*qcmp) (i, mid) <= 0)
  168.         i += qsz;
  169.         while (j > mid)
  170.         {
  171.         if ((*qcmp) (mid, j) <= 0)
  172.         {
  173.             j -= qsz;
  174.             continue;
  175.         }
  176.         tmp = i + qsz;    /* value of i after swap */
  177.         if (i == mid)
  178.         {        /* j <-> mid, new mid is j */
  179.             mid = jj = j;
  180.         }
  181.         else
  182.         {        /* i <-> j */
  183.             jj = j;
  184.             j -= qsz;
  185.         }
  186.         goto swap;
  187.         }
  188.         if (i == mid)
  189.         {
  190.         break;
  191.         }
  192.         else
  193.         {            /* i <-> mid, new mid is i */
  194.         jj = mid;
  195.         tmp = mid = i;    /* value of i after swap */
  196.         j -= qsz;
  197.         }
  198.     swap:
  199.         ii = qsz;
  200.         do
  201.         {
  202.         c = *i;
  203.         *i++ = *jj;
  204.         *jj++ = c;
  205.         } while (--ii);
  206.         i = tmp;
  207.     }
  208.     /* Look at sizes of the two partitions, do the smaller one first by
  209.        recursion, then do the larger one by making sure lo is its size,
  210.        base and max are update correctly, and branching back. But only
  211.        repeat (recursively or by branching) if the partition is of at
  212.        least size THRESH. */
  213.     i = (j = mid) + qsz;
  214.     if ((lo = j - base) <= (hi = max - i))
  215.     {
  216.         if (lo >= thresh)
  217.         qst(base, j);
  218.         base = i;
  219.         lo = hi;
  220.     }
  221.     else
  222.     {
  223.         if (hi >= thresh)
  224.         qst(i, max);
  225.         max = j;
  226.     }
  227.     } while (lo >= thresh);
  228. }
  229.